CF1114F Please, another Queries on Array?

状压+简单数论+简单线段树，一看就很套路。。。

题解：

首先思考欧拉函数的通项公式$\varphi(x)=x*\prod\limits_{i=1}^{n}(1-\frac{1}{p_i})$，其中$p_i$是$x$的质因数

也就是说对于要求的$\varphi(x)$，我们需要知道它的值$x$，和它的质因数$p_i$

考虑题目要求的查询$\varphi(\prod \limits_{i=l}^{r} a_i)$，根据上面的推理，要求出它我们也需要知道两样东西，$\prod \limits_{i=l}^{r} a_i$和区间$[l,r]$内有哪些质因数

乘积可以用线段树简单的维护，那有哪些质因数用什么维护呢？

注意到题目给出的$a_i$和$x$都很小，如果有经验的话（或者打个表）可以发现，这范围内只有62个质数

这不就是提示要状压吗！

于是线段树上开个longlong状压搞区间或就好了

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long
#define res pair<int,int>
#define x first //x是查询的乘积
#define y second //y是查询的状压

const int mod=1e9+7;
const int N=4e5+5;
int pn,p[70];
bool prime[350];
int a[N<<2],s[N<<2],mtg[N<<2],stg[N<<2],n,q,inv[70],sit[N],val[N];


int fpow(int x,int y,int mod){
    int mul=1;
    for(;y;y>>=1,mod?(x*=x)%=mod:x*=x) if(y&1) mod?(mul*=x)%=mod:mul*=x;
    return mul;
}

void init(int n){
    for(int i=2;i<=n;i++) prime[i]=1;
    for(int i=2;i<=n;i++){
        if(prime[i]) p[pn]=i,inv[pn++]=fpow(i,mod-2,mod);
        for(int j=0;j<pn&&i*p[j]<=n;j++){
            prime[i*p[j]]=0;
            if(i%p[j]==0) break;
        }
    }
}

void pushup(int x){
    a[x]=a[x<<1]*a[x<<1|1]%mod; //a是乘积
    s[x]=s[x<<1]|s[x<<1|1]; //s是状压
}

void build(int x,int l,int r){
    mtg[x]=1;
    stg[x]=0;
    if(l==r){
        a[x]=val[l];
        s[x]=sit[l];
        return ;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}

void pushdown(int x,int l,int r){
    int mid=l+r>>1;
    if(mtg[x]^1){ //乘上
        (mtg[x<<1]*=mtg[x])%=mod;
        (mtg[x<<1|1]*=mtg[x])%=mod;
        (a[x<<1]*=fpow(mtg[x],mid-l+1,mod))%=mod;
        (a[x<<1|1]*=fpow(mtg[x],r-mid,mod))%=mod;
        mtg[x]=1;
    }
    if(stg[x]){ //或上
        stg[x<<1]|=stg[x];
        stg[x<<1|1]|=stg[x];
        s[x<<1]|=stg[x];
        s[x<<1|1]|=stg[x];
        stg[x]=0;
    }
}

res merge(res x,res y){ //答案合并
    return res(x.x*y.x%mod,x.y|y.y);
}

res que(int x,int l,int r,int p,int q){
    if(p<=l&&r<=q){
        return res(a[x],s[x]);
    }
    pushdown(x,l,r);
    int mid=l+r>>1;
    res ans=res(1,0);
    if(p<=mid) ans=merge(ans,que(x<<1,l,mid,p,q));
    if(q>mid) ans=merge(ans,que(x<<1|1,mid+1,r,p,q));
    return ans;
}

void up(int x,int l,int r,int p,int q,int xv,int sv){
    if(p<=l&&r<=q){
        (a[x]*=fpow(xv,r-l+1,mod))%=mod;
        s[x]|=sv;
        (mtg[x]*=xv)%=mod;
        stg[x]|=sv;
        return ;
    }
    pushdown(x,l,r);
    int mid=l+r>>1;
    if(p<=mid) up(x<<1,l,mid,p,q,xv,sv);
    if(q>mid) up(x<<1|1,mid+1,r,p,q,xv,sv);
    pushup(x);
}

void doit(){
    char s[10];
    scanf("%s",s);
    int l,r;
    read(l);read(r);
    if(s[0]=='T'){
        res tp=que(1,1,n,l,r);
        for(int i=0;i<pn;i++) if(tp.y>>i&1)  //解压
            tp.x=tp.x*inv[i]%mod*(p[i]-1)%mod;
        write(tp.x);puts("");
    }
    else{
        int x,s=0;
        read(x);
        for(int i=0;i<pn;i++) if(x%p[i]==0) s|=1ll<<i;
        up(1,1,n,l,r,x,s);
    }
}

signed main(){
    init(300);
    read(n);read(q);
    for(int i=1;i<=n;i++){
        read(val[i]);
        for(int j=0;j<pn;j++) if(val[i]%p[j]==0)
            sit[i]|=1ll<<j; //分解出有哪些质因数搞状压
    }
    build(1,1,n);
    while(q--) doit();
}